// // vector
// // leetcode：118.杨辉三角   https://leetcode.cn/problems/pascals-triangle/description/
// #include <iostream>
// #include <vector>
// using namespace std;
// class Solution {
// public:
//     vector<vector<int>> generate(int numRows) {
//         vector<vector<int>>vv;
//         vv.resize(numRows);
//         for(int i = 0;i < numRows;i++)
//         {
//             vv[i].resize(i + 1, 0);
//             vv[i][0] = vv[i][i] = 1;
//         }
//         for(int i = 2;i < numRows;i++)
//         {
//             for(int j = 1;j < vv[i].size();j++)
//             {
//                 if(vv[i][j] == 0)
//                     vv[i][j] = vv[i-1][j-1] + vv[i-1][j];
//             }
//         }
//         return vv;
//     }
// };
// int main()
// {
//     int val = 0;
//     cin >> val;
//     vector<vector<int>>vv;
//     Solution s;
//     vv = s.generate(val);
//     for (int i = 0; i < vv.size(); i++)
//     {
//         for (int j = 0; j < vv[i].size(); j++)
//             cout << vv[i][j] << " ";
//         cout << endl;
//     }
//     return 0;
// }

// // 17.电话号码的字母组合
// // https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
// #include <vector>
// #include <string>
// using namespace std;
// class Solution {
// public:
//     string lcb[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//     void Combinations(string digits,int level,string strcombin,vector<string>&v)    // 注意：strcombin不能使用引用，因为该变量要记录字符串的情况，途中发生修改，则会破坏递归的逻辑
//     {
//         if(level == digits.size())                                                  // 结束条件：如果成立，说明已经构成了想要数目的字符串
//         {
//             v.push_back(strcombin);
//             return;
//         }

//         int num = digits[level]-'0';                                                // 截取给定字符串的数字，并变为整型
//         string str = lcb[num];                                                      // 锁定数字所对应的字符串
//         for(size_t i = 0;i < str.size();i++)
//         {
//             Combinations(digits,level+1,strcombin+str[i],v);                        // 递归组合字符串
//         }
//     }
//     vector<string> letterCombinations(string digits) {
//         vector<string>v;
        
//         if(digits.empty())  // 判断字符串是否为空
//             return v;
//         Combinations(digits,0,"",v);

//         return v;
//     }
// };

// // stack
// // nowcoder JZ31:栈的压入、弹出序列
// // https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
// #include <iostream>
// #include <vector>
// #include <stack>
// using namespace std;
// class Solution {
//   public:
//     bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
//         size_t push = 0, pop = 0;
//         stack<int> s;

//         // 1,2,3,4,5
//         // 4,3,5,2,1
//         while (push < pushV.size()) {
//             s.push(pushV[push++]);
//             while (!s.empty() && s.top() == popV[pop]) 
//             {
//                 s.pop();
//                 pop++;
//             }

//             // // 不匹配
//             // if (s.top() != popV[pop]) {
//             //     continue;
//             // }
//             // // 匹配
//             // else {
//             //     while (!s.empty() && s.top() == popV[pop]) {
//             //         s.pop();
//             //         pop++;
//             //     }
//             // }

//         }
//         return s.size() == 0;
//     }
// };
// int main()
// {
//     vector<int>v1 = {1,2,3,4,5};
//     vector<int>v2 = {4,3,5,2,1};
//     Solution s;
//     s.IsPopOrder(v1,v2);
//     system("pause");
//     return 0;
// }

// // stack：150.逆波兰表达式
// // https://leetcode.cn/problems/evaluate-reverse-polish-notation/
// #include <iostream>
// #include <vector>
// #include <string>
// #include <stack>
// using namespace std;
// class Solution {
// public:
//     int evalRPN(vector<string>& tokens) {
//         stack<int> s;
//         for(size_t i = 0;i < tokens.size();i++)
//         {
//             string& str = tokens[i];
//             // 操作符
//             if(str == "+" || str == "-" || str == "*" || str == "/")
//             {
//                 int left = s.top();
//                 s.pop();

//                 int right = s.top();
//                 s.pop();

//                 switch(str[0])
//                 {
//                     case '+':
//                         s.push(left + right);
//                         break;
//                     case '-':
//                         s.push(right - left);
//                         break;
//                     case '*':
//                         s.push(left * right);
//                         break;
//                     case '/':
//                         s.push(right / left);
//                         break;
//                 }
//                 // cout << left << " " << right << endl;
//                 // cout << s.top() << endl;

//             }
//             // 操作数
//             else
//             {
//                 // 利用atoi(字符转成整型)压入栈中
//                 s.push(atoi(str.c_str()));
//             }
//         }
//         return s.top();
//     }
// };

// // queue：102.二叉树的层序遍历Ⅰ
// // https://leetcode.cn/problems/binary-tree-level-order-traversal/
// #include<iostream>
// #include<vector>
// #include<queue>
// using namespace std;
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };
// class Solution {
// public:
//     vector<vector<int>> levelOrder(TreeNode* root) {
//         if(root == nullptr)
//             return {};
            
//         queue<TreeNode*>q;
//         int sizeTree = 0;
//         vector<vector<int>> vv;

//         if(root)
//         {
//             q.push(root);
//             sizeTree = 1;
//         }
//         while(!q.empty())
//         {
//             vector<int> v;
//             for(size_t i = 0;i < sizeTree;i++)
//             {
//                 TreeNode* front = q.front();
//                 v.push_back(front->val);
//                 q.pop();

//                 // cout << i << ":" << front->val << endl;

//                 if(front->left)
//                     q.push(front->left);
//                 if(front->right)
//                     q.push(front->right);
//             }
//             sizeTree = q.size();
//             vv.push_back(v);
//         }
//         return vv;
//     }
// };

// // queue：107.二叉树的层序遍历Ⅱ
// // https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/
// #include<iostream>
// #include<vector>
// #include<queue>
// #include<algorithm>
// using namespace std;
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };
// class Solution {
// public:
//     vector<vector<int>> levelOrder(TreeNode* root) {
//         if(root == nullptr)
//             return {};
            
//         queue<TreeNode*>q;
//         int sizeTree = 0;
//         vector<vector<int>> vv;

//         if(root)
//         {
//             q.push(root);
//             sizeTree = 1;
//         }
//         while(!q.empty())
//         {
//             vector<int> v;
//             for(size_t i = 0;i < sizeTree;i++)
//             {
//                 TreeNode* front = q.front();
//                 v.push_back(front->val);
//                 q.pop();

//                 // cout << i << ":" << front->val << endl;

//                 if(front->left)
//                     q.push(front->left);
//                 if(front->right)
//                     q.push(front->right);
//             }
//             sizeTree = q.size();
//             vv.push_back(v);
//         }
//         reverse(vv.begin(),vv.end());

//         return vv;
//     }
// };

// map：692.前k个高频单词
// https://leetcode.cn/problems/top-k-frequent-words/
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
public:
    struct greater
    {
        bool operator()(const pair<string, int>left, const pair<string, int>right)
        {
            return left.second > right.second || ((left.second == right.second) && (left.first < right.first));
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int>mp;                                             // 统计次数
        for (auto& data : words)                                  
        {
            mp[data]++;
        }

        vector<pair<string, int>>vp(mp.begin(), mp.end());               // 用来排序
        sort(vp.begin(), vp.end(), greater());
        vector<string>res;
        for (int i = 0; i < k;i++)
        {
            res.push_back(vp[i].first);
        }
        return res;
    }
};